package com.datastructures.tree;

/**
 * @author MaoLin Wang
 * @date 2019/11/719:01
 */
public class HeapSort {
    public static void main(String[] args) {


        //升序排序
        //int arr[]={4,6,8,5,9,10,2,53,11};

        //adjustHeap(arr,1,arr.length);
        //System.out.println(Arrays.toString(arr));
        //adjustHeap(arr,0,arr.length);
        //System.out.println(Arrays.toString(arr));





        //创建50000个随机数组
        int[] array =new int[8000000];
        for (int i=0;i<8000000;i++){
            array[i]=(int)(Math.random()*8000000);
        }

        long begintime=System.currentTimeMillis();
        System.out.println("开始时间"+begintime);

            heapSort(array);
       // System.out.println(Arrays.toString(arr));
        long endtime=System.currentTimeMillis();
        System.out.println("结束时间"+endtime);
        System.out.println("用时："+(endtime-begintime)+"ms");

    }

    public static void heapSort(int arr[]){
        int temp=0;
        /**
         * 构建大顶堆
         */
        for (int i = arr.length/2 -1;i>=0;i--){
            adjustHeap(arr,i,arr.length);
        }
      //  System.out.println(Arrays.toString(arr));

        /**
         * 将堆顶元素与末尾元素交换，将最大元素放到数组尾部
         * 重新调整堆，继续交换堆顶元素和末尾元素，此时末尾为刚刚的末尾的前一个
         */
        for (int j=arr.length-1;j>0;j--){
            //交换
            temp=arr[j];
            arr[j]=arr[0];
            arr[0]=temp;

            adjustHeap(arr,0,j);
        }
    }
    /**
     *  完成将 i对应的非叶子结点的树调整成大顶堆
     *
     *  如：i为1，则i对应的非叶子节点为6，对应的子树为6,5,9
     *      调整后为：4,9,8,5,6，调整结束后继续调整下一个非叶子结点
     *
     * @param arr 待排序数组
     * @param i 非叶字节点在数组中的索引
     * @param length 表示对多少个元素进行调整，因为length在逐渐减少
     */
    public  static void adjustHeap(int arr[],int i ,int length){

        //当前非叶子结点
        int temp=arr[i];

        /**
         * k 为 当前节点的左孩子
         */
        for (int k = i * 2 + 1; k < length; k = k*2+1){
            if ( ( k + 1 ) < length && arr[k] < arr[k+1]){//左孩子小于右孩子
                k ++ ;//k指向右孩子
            }
            if (arr[k] > temp){//指向的较大的这个节点比当前temp节点还大
                arr[i]=arr[k];
                i = k; //i指向k继续循环比较

            }else {
                break;
            }
        }
        //已经将i为父节点的树的最大值，放在了该子树的最顶上

        //将temp放在最后的位置arr[i]
        arr[i] = temp;
    }



}
